【题解】 [HNOI/AHOI2018]转盘 线段树 luoguP4425

首先再来讲明一下题意：

给定一个长度为 $n$ 的环，环上的每个点有一个权值 $T_i$ ，要求你从环上选中任意一个点为起点开始，每个时间可以顺时钟到下一个点，或者停留不动。对于一个点，如果到这个点的时间大于等于了 $T_i$ ，那么这个点将被标记，问最少什么时候可以让所有物品都被标记。

可以发现，这个问题的答案跟以下问题的答案是等价的：

给定一个长度为 $n​$ 的环，环上的每个点有一个权值 $T_i​$ ，要求你从环上选中任意一个点为起点开始，，开始的时间为 $t​$ ，每个时间可以逆时针到下一个点，或者停留不动。对于一个点，它将在 $T_i​$ 时间损坏 ，求一个最小的 $t​$ 使得我们能够在没有点损坏的情况下遍历所有点。

我们算一下每一个点离起点的距离，那么这个时候我们就可以在起点等，等一段时间后再出发，这样子我们转一圈就够了，这个方案显然是最优的。

我们断环为链，枚举起点 $s$ ，对于一个点 $i$ ，$s$ 到达 $i$ 的耗时显然是 $(i-s)$ ，那么我们如果想要等一段时间出发后正好标记该点，这一段等待的时间当然就是 $T_i-(i-s)$ 。我们对所有的点 $i$ 的 $T_i-(i-s)$ 取 $max$ ，最后的结果就是我们应该在 $s$ 等的时间。

那么很显然我们的答案为：

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-(i-s)] \}+n-1$$

$min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-(i-s)] \}​$ 这显然是在选择一个最优的起点使得等待时间最小，$n-1​$ 就是等待完后转一圈的时间。

这个时候暴力枚举就可以得到 $30$ 分。

不过我们继续：

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-i+s] \}+n-1$$

我们设 $A_i$ 为 $T_i-i$ 。

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[A_i+s] \}+n-1$$

假设现在有一对 $A_i,A_{i+n}$ ，我们可以发现 $A_{i+1}$ 是必然比 $A_i$ 小的，也就是说 $A_{s+n}$ 到 $A_{2n}$ 这一段数就算算进来也造不成影响。

也就是说原式跟这个式子是等价的：

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,2n]}[A_i+s] \}+n-1$$

发现 $max$ 里面 $s$ 并没有什么卵用，直接提出来。

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,2n]}A_i +s\}+n-1​$$

这个的话……因为 $A_i$ 的值跟 $s$ 没有关系……所以……所以我们可以预处理一个 $ST$ 表……嗯……然后枚举 $s$ ……结果我们是 $O(n)$ 搞定？？？

哦哦哦作者脑抽了，这题是待修改的。

不过没关系，我们还有出路。

现在考虑用线段树来维护，假设结点 $x$ 代表的区间为 $l,r$ ，维护一个 $val[x]$ 表示区间 $[l,r]$ 中 $A_i$ 的最大值，这个是线段树基本操作不再赘述，然后再维护一个 $ans[x]$ 表示区间 $min_{s \in [l,mid]}\{ max_{i \in [s,r]} \}$ 。$1$ 号结点的区间为 $1,2n$ ，我们的答案就是 $ans[1]$ 。

那么怎么上传 $ans$ 呢。

我们对于 $[mid,r]$ 区间的最大值 $A_x$ ，这个 $A_x$ 显然可以 $O(1)$ 求出，然后再找到一个 $A_y$ ，表示当 $s$ 为 $y$ 的时候，整个 $[s,r]$ 的 $A_i$ 的最大值为 $A_x$ 。在寻找 $y$ 的时候顺便更新一下 $s\in [l,y-1]$ 的区间的答案就好。

当 $s\in [y,r]​$ 的时候答案明显为 $A_x+s​$ ，要满足最小嘛。

有关这一部分的代码实现：

inline void calc(int k,int l,int r,int Ax){
    if(l==r)return l+max(val[k],Ax);
    int mid=(l+r)>>1;
    else if(val[k<<1|1]>=Ax)return min(calc(k<<1|1,mid+1,r,Ax),ans[k<<1]);
    else return min(calc(k<<1,l,mid,Ax),(mid+1)+Ax);
}

我们来剖析一下代码。

inline void calc(int k,int l,int r,int Ax){

这一句表示当前的结点为 $k$ ，$k$ 代表的区间为 $l,r$ ，$Ax$ 为上文中的 $A_x$ 。

if(l==r)return l+max(val[k],Ax);

这个显然就是找到了 $y$ ，这个时候答案为 $A_x+s$ ，上文也讲了，这里的 $s$ 就是 $y$ 的位置，$A_x$ 已经在函数中了直接调用就好。但是为什么要取 $max$ 呢？因为怕 $A_y$ 是大于 $A_x$ 的! ，所以加个 $max$ 就好。

else if(val[k<<1|1]>=Ax)return min(calc(k<<1|1,mid+1,r,Ax),ans[k<<1]);

这个就是当前结点的右区间有比 $A_x$ 大的数，那么这个时候 $y$ 就不可能到左区间去了，不然的话 $[y,r]$ 中 $max\{A_i\}$ 就不是 $A_x$ 了，所以我们往右子树走。这个时候可以发现 $s$ 属于左区间的时候的答案为 $ans[k<<1]$ ，顺带更新一下。

else return min(calc(k<<1,l,mid,Ax),(mid+1)+Ax);

这个时候 $y$ 就是在左区间了，那么我们往左区间走，右区间的答案呢？右区间为 $[mid,r]$ ，显然这一段的最大值肯定都为 $A_x$ ——包括 $mid+1$ ，所以不要跟 $mid+1$ 取一下 $max$ 了——尽管第一句是与 $A_y$ 取了 $max$ 的。

这个时候因为要 $s$ 尽量的小，所以就是右区间的左端点——$mid+1$ 了。

这个时候 $pushup$ 就应该这么写：

inline void pushup(int x,int l,int r){
    val[x]=max(val[x<<1],val[x<<1|1]);
    int mid=(l+r)>>1;
    ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
}

Code:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long ll;

const int N=4e5+2;
const int inf=1e9+9;

int n,m,p,lastans,a[N];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct Seg_Tree{
    #define mid ((l+r)>>1)
    int ans[N<<2],val[N<<2];
    int calc(int x,int l,int r,int Mx){
        if(l==r)return l+max(val[x],Mx);
        if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
        else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
    }
    inline void pushup(int x,int l,int r){
        val[x]=max(val[x<<1],val[x<<1|1]);
        ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
    }
    inline void build(int x,int l,int r){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x,l,r);return;
    }
    inline void updata(int x,int l,int r,int pos){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        if(pos<=mid)updata(x<<1,l,mid,pos);
        else if(pos>mid)updata(x<<1|1,mid+1,r,pos);
        pushup(x,l,r);
    }
}T;

int main(){
    IN(n),IN(m),IN(p);
    for(int i=1;i<=n;++i)IN(a[i]),a[i+n]=a[i];
    for(int i=1;i<=(n<<1);++i)a[i]-=i;
    T.build(1,1,(n<<1));	
    lastans=T.ans[1]+n-1,printf("%d\n",lastans);
    for(int i=1;i<=m;++i){
        int x,y;IN(x),IN(y);
        if(p)x^=lastans,y^=lastans;
        a[x]=y-x,a[x+n]=y-x-n;
        T.updata(1,1,(n<<1),x),T.updata(1,1,(n<<1),x+n);
        printf("%d\n",lastans=T.ans[1]+n-1);
    }
    return 0;
}

但是这份代码是 TLE 的。

这玩意坑了我好久，你知道为什么 TLE 吗？

就是这个鬼东西！：

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))

这里的 $x$ 和 $y$ 是调用了两次的，然后我们发现 $calc$ 函数……

int calc(int x,int l,int r,int Mx){
    if(l==r)return l+max(val[x],Mx);
    if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
    else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
}

$min$ 里面有 $calc$ 函数………..然后 $calc$ 函数调用了两次……….然后………..爆炸！

所以 $Qiuly$ 提醒您：代码千万条，时间第一条，$define$ 不规范，$OIer$ 两行泪 。

还是跟着 $std$ 走好嘿嘿嘿，$using\ namespace\ std$ 万岁！

最终 $AC$ 的代码。

Code:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=4e5+2;
const int inf=1e9+9;

int n,m,p,lastans,a[N];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct Seg_Tree{
    #define mid ((l+r)>>1)
    int ans[N<<2],val[N<<2];
    int calc(int x,int l,int r,int Mx){
        if(l==r)return l+max(val[x],Mx);
        if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
        else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
    }
    inline void pushup(int x,int l,int r){
        val[x]=max(val[x<<1],val[x<<1|1]);
        ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
    }
    inline void build(int x,int l,int r){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x,l,r);return;
    }
    inline void updata(int x,int l,int r,int pos){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        if(pos<=mid)updata(x<<1,l,mid,pos);
        else if(pos>mid)updata(x<<1|1,mid+1,r,pos);
        pushup(x,l,r);
    }
}T;

int main(){
    IN(n),IN(m),IN(p);
    for(int i=1;i<=n;++i)IN(a[i]),a[i+n]=a[i];
    for(int i=1;i<=(n<<1);++i)a[i]-=i;
    T.build(1,1,(n<<1));	
    lastans=T.ans[1]+n-1,printf("%d\n",lastans);
    for(int i=1;i<=m;++i){
        int x,y;IN(x),IN(y);
        if(p)x^=lastans,y^=lastans;
        a[x]=y-x,a[x+n]=y-x-n;
        T.updata(1,1,(n<<1),x),T.updata(1,1,(n<<1),x+n);
        printf("%d\n",lastans=T.ans[1]+n-1);
    }
    return 0;
}

本文标题:【题解】 [HNOI/AHOI2018]转盘 线段树 luoguP4425

文章作者:Qiuly

发布时间:2019年03月20日 - 00:00

最后更新:2019年03月29日 - 13:55

原始链接:http://qiulyblog.github.io/2019/03/20/[题解]luoguP4425/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

题解 线段树

【题解】 历史研究 回滚莫队 luoguAT1219

【题解】 [Violet]天使玩偶/SJY摆棋子 K-D Tree luoguP4169/bzoj2648